class Solution {
public:

    // Encodes a tree to a single string.
    string s;
    string serialize(TreeNode* root) {
        dfs(root);
        return s;
    }
    void dfs(TreeNode* root){
        if(!root) {
            s += "null ";
            return;
        }
        s += to_string(root->val) + ' ';
        dfs(root->left);
        dfs(root->right);
    }

    // Decodes your encoded data to tree.
     TreeNode* deserialize(string data) {
        int u = 0;
        return dfs_d(data, u);
    }

    TreeNode* dfs_d(string& data, int &u)
    {
        if(data.size() == 0) return NULL;
        int k = u;
        while(data[k] != ' ') k++;
        //当前开始是null，节点不必往下递归了，u = k + 1
        if(data[u] == 'n'){
            u = k + 1;
            return NULL;
        }
        int sign = 1,val = 0;
        if(u < k && data[u] == '-') u++,sign = -1;
        for(int i = u;i < k;i++) val = val * 10 + data[i] - '0';
        val *= sign;
        u = k + 1;
        auto root = new TreeNode(val);
        root->left = dfs_d(data,u);
        root->right = dfs_d(data,u);
        return root;
    }
};